1. Field of the Invention
The present invention relates generally to an ad-hoc network and a method for routing extension. More particularly, the present invention relates to an ad-hoc network for routing data to Internet via a gateway and a method for routing extension.
2. Description of the Related Art
Typically, a mobile communication system delivers data between a mobile element and a base station. The mobile element directly transmits to and receives from the base station data without passing through any other mobile elements or nodes. Meanwhile, when data originated from a certain node are transmitted to a gateway over an ad-hoc network, other nodes are used. A construction of an ad-hoc network is described with reference to FIG. 1. As illustrated in FIG. 1, the ad-hoc network is connectable to Internet to allow data transmission to Internet. The ad-hoc network includes a gateway for transmitting data to Internet and a plurality of nodes. Although FIG. 1 illustrates only one gateway, the ad-hoc network may include at least two gateways according to a user's setting, or the ad-hoc network may be compromised without a gateway.
The gateway is responsible for delivering data from the nodes in the ad-hoc network to another communication system (Internet network). The plurality of the nodes transmits packets to the gateway. A node which can directly communicate with the gateway transmits data directly to the gateway. A node which can access the gateway via more than one intermediate node transmits its collected data to a neighboring node which is located on the path between the node and the gateway. One of the main reasons to use a neighboring node is to minimize the power consumption required for data transmission. The power consumed in transmitting data is proportional to the distance between a gateway a the node. Accordingly, the nodes beyond a certain distance from the gateway transmit their collected data via a plurality of other nodes to minimize the power consumption for data transmission.
The following is an explanation of how a node establishes a data transmission path (hereinafter, also referred to as routing) to a gateway in an ad-hoc network. The data routing consists of four stages:                Gateway solicitation process;        Gateway advertisement process;        Generating global address for Internet; and        Sending data        
Hereafter, the routing stages for data transmission are illustrated in order with reference to FIG. 2. In the gateway solicitation process, a node entering the ad-hoc network requests a route to the gateway (S200). The node needs to be aware of a route to the gateway so as to transmit data to the gateway. The node broadcasts a message containing its address information and requesting the address of the gateway. Neighboring nodes receiving the message determine whether they are the gateway requested by the node. Mostly, the gateway knows that itself is the requested gateway. If the neighboring nodes determine that they are not the requested gateway, they update and retransmit the received message to other neighboring nodes. At this time, the neighboring nodes obtain from the received message and store information about the path to the source node originating the message. When the message is retransmitted, the source address of the message is changed to the address of the node that updates and retransmits the message. In that way, the message originated from a node is delivered to the gateway in an ad-hoc network. The gateway learns from the information contained in the received message that the node requests an advertisement. Therefore, the message originated from a node can be delivered to at least one gateway in the ad-hoc network.
After the gateway solicitation process, the ad-hoc network performs the gateway advertisement process (S202). In the gateway advertisement process, the gateway, receiving the message originated from the node, transmits its address information to the node. The gateway extracts the address information of the node from the message received during the gateway solicitation process. The gateway transmits a message containing its address information to a node corresponding to the extracted address information. Unlike in the gateway solicitation process, the messages are unicasted in the gateway advertisement process. That is, a message transmitted from the gateway is unicasted to a node using the path information obtained during the gateway solicitation process. Nodes forwarding the message store information about the path to the gateway. Nodes receiving the message originated from the gateway count the number of hops. Specifically, nodes receiving the message add one to the number of hops contained in the message received from the previous node and forwards the message containing the number of the increased hops to a next node. Therefore, the node requesting the path information of the gateway can acquire the path information of the gateway and the number of hops to the gateway. It is noted that, as for a plurality of gateways, the node acquires information relating to each of the gateways.
In configuring a global address for Internet, the node configures its unique address using the acquired information (S204). When the gateway for data transmission is selected, the node sends, data along the established path (S206).
In the gateway advertisement process, a gateway may frequently broadcast to all nodes in the ad-hoc network. In that case, a node receiving the advertisement message can directly configure its unique address and establish a route to the gateway. A node which intends to send a packet to Internet may directly access to the gateway.
With the advent of ad-hoc networks, home networks, sensor networks, and the like, and the network extension therefrom through connection to Internet, the protocols for addressing and data routing for the networks also have been extended. In this regard, an extended routing method is demanded.
In a conventional ad-hoc network for transmitting data to Internet, routing extension can be carried out by two methods. FIG. 3A illustrates a conventional routing extension method, in which Address REQuest (AREQ) and Address REPly (AREP) messages are used. For this method, an existing routing protocol is modified so as to enable address configuration. With reference to FIG. 3A, a node sends an AREQ message to a gateway and receives an AREP message from the gateway to establish a global address and a data transmission path. The AREQ and AREP messages further contain information for address configuration appended to Routing REQuest (RREQ) and Routing REPly (RREP) messages, but lack information required to configure a complete global address. Hence, with the AREQ and AREP method, a complete route can be established, but the address configuration cannot be complete.
FIG. 3B illustrates another conventional routing extension method which uses the modified Routing Solicitation (RS) and Routing Advertisement (RA) messages. For this method, the existing Internet Protocol version 6 (IPv6) for address configuration is modified so as to make routing possible. As shown in FIG. 3B, a node sends an RS message to a gateway and receives an RA message from the gateway to generate its global address and establish a data transmission path. The RS and RA messages which are used for address configuration do not contain information required for routing. In addition, since the conventional RS and RA messages cause change of the address of the source node if the message is delivered beyond one hop, a separate multicasting method is required. Therefore, control message overhead to maintain a separate multicast tree occurs and the routing becomes unstable.